import java.util.Arrays;
import java.util.Scanner;

public class BinarySearchOne {
    /**
     * 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，
     * 写一个函数搜索 nums 中的 target，
     * 如果目标值存在但是存在重复的，返回第一个元素的下标位置
     */
    // 典型的二分查找的问题，只是找到中间的target值之后还需要向左返回第一个元素的下标位置吧
    public static int searchOne(int []nums,int target){
        Arrays.sort(nums);
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = (left + right) / 2;

            if (nums[mid] == target) {
                // 如果中间元素等于目标值，向左继续查找第一个出现的位置
                while (mid > 0 && nums[mid - 1] == target) {
                    mid--;
                }
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return -1; // 目标值不存在于数组中
    }

    public static void main(String[] args) {
        // 自定义输入输出
        Scanner in=new Scanner(System.in);
        System.out.print("请输入数组的长度：");
        int n=in.nextInt();
        int []nums=new int[n];
        System.out.print("请依次输入数组元素：");
        for(int i=0;i<nums.length;i++){
            nums[i]=in.nextInt();
        }
        System.out.println(Arrays.toString(nums));

        System.out.print("输入需要查找的目标字符：");
        int target=in.nextInt();
        int firstPosition=searchOne(nums,target);
        System.out.println("出现的第一个位置下标是: " + firstPosition); // 输出：2

    }
}
